package com.company.algo.DichotomousSearch;

import java.util.Arrays;

/**
 * 410. 分割数组的最大值
 反向思考这道题。
 现在题目是固定了m的值，让我们确定一个最大子数组和；
 所谓反向思考就是说，我们可以反过来，限制一个最大子数组和max，来反推最大子数组和为max时，至少可以将nums分割成几个子数组。
 */
public class SplitArray {
    //将问题转化为给定max，求至少需要划分多少个子数组
    public int splitArray(int[] nums, int m) {
        int lo = Arrays.stream(nums).max().getAsInt();
        int hi = Arrays.stream(nums).sum()+1;
        while (lo < hi){
            int mid = lo + (hi - lo)/2;
            int n = split(nums,mid);
            if (n <= m) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private int split(int[] nums, int max) {
        int count = 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum + nums[i] > max) {
                sum = nums[i];
                count++;
            }else {
                sum += nums[i];
            }
        }
        return count;
    }
}
